package cn.suchan.jianzhi.q23_bst;

import java.util.Arrays;

/**
 * 知识点：二叉搜索树的后序遍历序列
 * 题目描述
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 * <p>
 * 二叉搜索树特点：
 * ①若该树非空，且其左子树非空，则左子树上所有节点的值均小于其根节点的值；
 * ②若该树非空，且其右子树非空，则右子树上所有节点的值均大于其根节点的值；
 * ③若该树非空，则其任意节点的左右子树均为二叉搜索树；
 * ④该树中任意节点的值均不相等。
 * </p>
 *
 * @author suchan
 * @date 2019/05/28
 */
public class Solution {

    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length <= 0) {
            return false;
        }
        // 二叉搜索树中任意节点的值均不相等
        for (int i = 0; i < sequence.length - 1; i++) {
            for (int j = i + 1; j < sequence.length; j++) {
                if (sequence[i] == sequence[j]) {
                    return false;
                }
            }
        }
        int length = sequence.length;
        // 根节点值
        int rootVal = sequence[length - 1];
        // 左子树结束节点的下标
        int leftEnd = 0;
        // 左子树的所有节点的值都小于根节点的值，
        // 所以当出现一个大于或等于根节点的值之后，就不属于左子树的节点了
        for (int i = 0; i < length - 1; i++) {
            if (sequence[i] >= rootVal) {
                break;
            }
            leftEnd = i;
        }

        // 右子树开始节点的下标
        int rightStart = leftEnd + 1;
        // 右子树的所有节点的值都大于根节点的值，
        // 所以当右子树中出现一个小于或等于根节点的值，则表明该后序遍历序列有误
        for (int i = rightStart; i < length - 1; i++) {
            if (sequence[i] <= rootVal) {
                return false;
            }
        }

        // 能执行到这一步说明这棵树的这一部分是没有问题了，所以leftFlag和rightFlag为true
        // 因为左子树是挑选了小于根节点的一些节点，所以不需要验证
        boolean leftFlag = true;
        if (leftEnd > 0) {
            // copyOfRange()包含from不包含to
            leftFlag = VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, leftEnd + 1));
        }

        boolean rightFlag = true;
        if (rightStart < length - 1) {
            rightFlag = VerifySquenceOfBST(Arrays.copyOfRange(sequence, rightStart, length - 1));
        }

        return leftFlag && rightFlag;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 5, 4, 7, 10, 8, 9, 6};
        Solution solution = new Solution();
        System.out.println("result==>" + solution.VerifySquenceOfBST(arr));
    }
}
